#!/usr/bin/python

"""Project Euler Solution 055

Copyright (c) 2011 by Robert Vella - robert.r.h.vella@gmail.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""

import cProfile
from euler.list_functions import ispalindrome    
from euler.numbers.decimal_base import integer_to_digits, join_integers

def get_answer():
    """Question:
    
    If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

    Not all numbers produce palindromes so quickly. For example,
    
    349 + 943 = 1292,
    1292 + 2921 = 4213
    4213 + 3124 = 7337
    
    That is, 349 took three iterations to arrive at a palindrome.
    
    Although no one has proved it yet, it is thought that some numbers, like 
    196, never produce a palindrome. A number that never forms a palindrome 
    through the reverse and add process is called a Lychrel number. Due to 
    the theoretical nature of these numbers, and for the purpose of this 
    problem, we shall assume that a number is Lychrel until proven otherwise. 
    In addition you are given that for every number below ten-thousand, it will 
    either (i) become a palindrome in less than fifty iterations, or, 
    (ii) no one, with all the computing power that exists, has managed so far 
    to map it to a palindrome. In fact, 10677 is the first number to be shown 
    to require over fifty iterations before producing a palindrome: 
    4668731596684224866951378664 (53 iterations, 28-digits).
    
    Surprisingly, there are palindromic numbers that are themselves Lychrel 
    numbers; the first example is 4994.
    
    How many Lychrel numbers are there below ten-thousand?
    
    NOTE: Wording was modified slightly on 24 April 2007 to emphasise the 
    theoretical nature of Lychrel numbers.
    """
    def islychrel_number(n):
        """Returns true if [n] is a Lychrel number."""
        
        def inner_islychrel(n, iterations):
            """Returns true if [n] is a Lychrel number, or [iterations] is
            greater than or equal to 50."""
            
            #Return true if the iteration limit has been exceeded.
            if iterations > 49:
                return True
            
            #Return true if the next number in the series is a Lychrel number, 
            #or false if this number is a palindrome and not the original 
            #number tested.
            digits = list(integer_to_digits(n))
            
            if ispalindrome(digits) and iterations > 0:
                return False
            
            digits.reverse()
            reversed_number = join_integers(digits)
                    
            return inner_islychrel(n + reversed_number, iterations + 1)
        
        #Return true if [n] is a Lychrel number.
        return inner_islychrel(n, 0)
    
    #Return result.
    return sum(1 for n in range(10001) if islychrel_number(n))
    
if __name__ == "__main__":
    cProfile.run("print(get_answer())")
